package q1584_minCostConnectPoints;

import CommonClass.UF;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class Solution {
    /*
    并查集和 Kruskal 算法的结合 与第1135题完全相同
     */
    public int minCostConnectPoints(int[][] points) {
        List<int[]> edges = new ArrayList<>();
        for (int i = 0; i < points.length; i++) {
            for (int j = i + 1; j < points.length; j++) {
                edges.add(new int[]{getDistance(points, i, j), i, j});
            }
        }

        edges.sort(Comparator.comparingInt(a -> a[0]));
        UF uf = new UF(points.length);
        int res = 0;
        for (int[] edge : edges) {
            int pay = edge[0];
            int i = edge[1];
            int j = edge[2];
            if (!uf.isConnected(i, j)) {
                uf.union(i, j);
                res += pay;
            }
        }
        return res;
    }
    private int getDistance(int[][] points, int i, int j) {
        int[] p1 = points[i], p2 = points[j];
        return Math.abs(p1[0] - p2[0]) + Math.abs(p1[1] - p2[1]);
    }
}
